package day0415;

import java.util.ArrayList;
import java.util.List;

public class LeetCode22 {
    /**
     * 22. 括号生成  dfs
     * 中等
     * 相关标签
     * 相关企业
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * 示例 2：
     * <p>
     * 输入：n = 1
     * 输出：["()"]
     */
    public static void main(String[] args) {

        System.out.println(generateParenthesis(3));
    }

    private static List<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int left = 0;
        int right = 0;
        dfs(left, right, n, list, sb);
        return list;
    }

    private static void dfs(int left, int right, int n, List<String> list, StringBuilder sb) {
        if (left > n || right > n || right > left) {
            return;
        }
        if (sb.length() == 2 * n && left == right) {
            list.add(sb.toString());
        }
        sb.append('(');
        dfs(left + 1, right, n, list, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(')');
        dfs(left, right + 1, n, list, sb);
        sb.deleteCharAt(sb.length() - 1);
    }

}
